ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/doc/needle-haystack.tex

   1 \section{32 - A needle in the haystack}
   2
   3 \textbf{Problema:} Encontrar todas las ocurrencias de una cadena $s$ en otra cadena $t$.
   4
   5 \subsection{Resoluci\'on}
   6
   7 La resoluci\'on es directa usando Knuth-Morris-Pratt. El enunciado anticipa que $t$
   8 es potencialmente muy grande. En lugar de reservar memoria para leer la cadena $t$ completa,
   9 se trabaja con un buffer de tama\~no fijo (e independiente de la entrada).
  10
  11 La elecci\'on del tama\~no del buffer s\'olo modifica el tiempo de ejecuci\'on
  12 en una constante. El tama\~no del buffer incluso podr\'ia ser 1. Esto es posible
  13 porque el algoritmo KMP accede a las posiciones de $t$ de manera creciente.
  14
  15 Primero se construye la funci\'on de falla $F$ asociada a la cadena $s$,
  16 de tal manera que:
  17 $$F(i) = \text{longitud del sufijo m\'as largo de $s[0..i)$ que tambi\'en es prefijo de $s[0..i-1)$}$$
  18
  19 \begin{figure}[H]
  20 \centering
  21 \includegraphics[scale=0.5]{./figuras/kmp.pdf}
  22
  23 \begin{tabular}{l|rrrrrrr}
  24 \hline
  25 $e$    &  0 & 1 & 2 & 3 & 4 & 5 & 6 \\
  26 $F(e)$ & -1 & 0 & 1 & 0 & 1 & 2 & 3 \\
  27 \hline
  28 \end{tabular}
  29 \caption{Aut\'omata impl\'icito en la cadena $aabaab$ (l\'ineas s\'olidas) y la funci\'on de falla $F$ (l\'ineas punteadas)}
  30 \end{figure}
  31
  32 La cadena $s$ y la funci\'on de falla pueden interpretarse como un aut\'omata.
  33 Para buscar las ocurrencias de $s$ en $t$, si se est\'a en el estado $e$ y el
  34 caracter de entrada coincide con $s[e]$, se avanza al estado $e + 1$.
  35 Si el caracter de entrada difiere de $s[e]$, se vuelve al estado $F(e)$
  36 y se repite el proceso. (Si en alg\'un momento se llega al estado -1, el
  37 caracter actual se descarta y se pasa al estado 0).
  38
  39 Dado que la funci\'on de falla cumple que $F(e) < e$ para todo $e$,
  40 y que cada vez que se incrementa el estado se lee un caracter de la
  41 entrada, la cantidad total de retrocesos no puede ser mayor que $|t|$.
  42 Adem\'as, la construcci\'on de la tabla de $F$ es $O(|s|)$. (La
  43 tabla se construye de la manera usual).
  44
  45 Por lo tanto, la complejidad temporal del algoritmo es $O(|s| + |t|)$.
  46 La memoria utilizada es $O(|s|)$ para almacenar la tabla de $F$ y
  47 un buffer de tama\~no constante (64 KB).
  48
  49 \subsection{Implementación}
  50 \noindent
  51 \ttfamily
  52 \shorthandoff{"}\\
  53 \hlstd{}\hlline{\ 1\ }\hldir{\#include\ $<$vector$>$}\\
  54 \hlline{\ 2\ }\hlstd{}\hldir{\#include\ $<$string$>$}\\
  55 \hlline{\ 3\ }\hlstd{}\hldir{\#include\ $<$iostream$>$}\\
  56 \hlline{\ 4\ }\hlstd{}\hldir{\#include\ $<$cassert$>$}\\
  57 \hlline{\ 5\ }\hlstd{}\hldir{\#include\ $<$cstdlib$>$}\\
  58 \hlline{\ 6\ }\hlstd{}\\
  59 \hlline{\ 7\ }\hlkwa{using\ namespace\ }\hlstd{std}\hlsym{;}\\
  60 \hlline{\ 8\ }\hlstd{}\\
  61 \hlline{\ 9\ }\hlkwc{typedef\ }\hlstd{}\hlkwb{unsigned\ long\ long\ int\ }\hlstd{lluint}\hlsym{;}\\
  62 \hlline{10\ }\hlstd{}\hlkwc{typedef\ }\hlstd{vector}\hlsym{$<$}\hlstd{}\hlkwb{int}\hlstd{}\hlsym{$>$\ }\hlstd{vint}\hlsym{;}\\
  63 \hlline{11\ }\hlstd{}\\
  64 \hlline{12\ }\hldir{\#define\ forsn(i,\ s,\ n)\ for\ (int\ i\ =\ (s);\ i\ $<$\ (n);\ i++)}\\
  65 \hlline{13\ }\hlstd{}\hldir{\#define\ forn(i,\ n)\ forsn\ (i,\ 0,\ n)}\\
  66 \hlline{14\ }\hlstd{}\\
  67 \hlline{15\ }\hlslc{//\ Pre\ KMP}\\
  68 \hlline{16\ }\hlstd{}\\
  69 \hlline{17\ }\hlkwb{void\ }\hlstd{}\hlkwd{pkmp}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{string}\hlsym{\&\ }\hlstd{s}\hlsym{,\ }\hlstd{vint}\hlsym{\&\ }\hlstd{f}\hlsym{)\ \{}\\
  70 \hlline{18\ }\hlstd{\ }\hlkwb{int\ }\hlstd{z\ }\hlsym{=\ }\hlstd{f}\hlsym{{[}}\hlstd{}\hlnum{0}\hlstd{}\hlsym{{]}\ =\ {-}}\hlstd{}\hlnum{1}\hlstd{}\hlsym{;}\\
  71 \hlline{19\ }\hlstd{\ }\hlkwd{forsn\ }\hlstd{}\hlsym{(}\hlstd{i}\hlsym{,\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{,\ }\hlstd{s}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{()\ +\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{)\ \{}\\
  72 \hlline{20\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{z\ }\hlsym{!=\ {-}}\hlstd{}\hlnum{1\ }\hlstd{}\hlsym{\&\&\ }\hlstd{s}\hlsym{{[}}\hlstd{i\ }\hlsym{{-}\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{{]}\ !=\ }\hlstd{s}\hlsym{{[}}\hlstd{z}\hlsym{{]})\ }\hlstd{z\ }\hlsym{=\ }\hlstd{f}\hlsym{{[}}\hlstd{z}\hlsym{{]};}\\
  73 \hlline{21\ }\hlstd{}\hlstd{\ \ }\hlstd{f}\hlsym{{[}}\hlstd{i}\hlsym{{]}\ =\ ++}\hlstd{z}\hlsym{;\ }\hlstd{}\hlslc{//\ z\ might\ be\ {-}1}\\
  74 \hlline{22\ }\hlstd{\ }\hlsym{\}}\\
  75 \hlline{23\ }\hlstd{}\hlsym{\}}\\
  76 \hlline{24\ }\hlstd{}\\
  77 \hlline{25\ }\hlslc{//\ Buffer}\\
  78 \hlline{26\ }\hlstd{}\\
  79 \hlline{27\ }\hldir{\#define\ TAMBUF\ 65536}\\
  80 \hlline{28\ }\hlstd{lluint\ pos}\hlsym{;}\\
  81 \hlline{29\ }\hlstd{}\hlkwb{char\ }\hlstd{buf}\hlsym{{[}}\hlstd{TAMBUF}\hlsym{{]};}\\
  82 \hlline{30\ }\hlstd{}\hlkwb{int\ }\hlstd{buf\textunderscore size}\hlsym{;}\\
  83 \hlline{31\ }\hlstd{}\\
  84 \hlline{32\ }\hldir{\#define\ buf\textunderscore sync()\ \{\ $\backslash$}\\
  85 \hlline{33\ }\hldir{\ cin.getline(buf,\ TAMBUF\ +\ 1);\ $\backslash$}\\
  86 \hlline{34\ }\hldir{\ pos\ +=\ buf\textunderscore size;\ $\backslash$}\\
  87 \hlline{35\ }\hldir{\ buf\textunderscore size\ =\ cin.gcount();\ $\backslash$}\\
  88 \hlline{36\ }\hldir{\ cin.clear();\ $\backslash$}\\
  89 \hlline{37\ }\hldir{\}}\\
  90 \hlline{38\ }\hlstd{}\\
  91 \hlline{39\ }\hldir{\#define\ buf\textunderscore start()\ \{\ $\backslash$}\\
  92 \hlline{40\ }\hldir{\ buf\textunderscore sync();\ $\backslash$}\\
  93 \hlline{41\ }\hldir{\ pos\ =\ 0;\ $\backslash$}\\
  94 \hlline{42\ }\hldir{\}}\\
  95 \hlline{43\ }\hlstd{}\\
  96 \hlline{44\ }\hlslc{//\ KMP}\\
  97 \hlline{45\ }\hlstd{}\\
  98 \hlline{46\ }\hlkwb{void\ }\hlstd{}\hlkwd{kmp}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{string}\hlsym{\&\ }\hlstd{s}\hlsym{,\ }\hlstd{vint}\hlsym{\&\ }\hlstd{f}\hlsym{)\ \{}\\
  99 \hlline{47\ }\hlstd{\ }\hlkwd{buf\textunderscore start}\hlstd{}\hlsym{();}\\
 100 \hlline{48\ }\hlstd{\ }\hlkwb{const\ int\ }\hlstd{final\ }\hlsym{=\ }\hlstd{s}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{();}\\
 101 \hlline{49\ }\hlstd{\ }\hlkwb{int\ }\hlstd{state\ }\hlsym{=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{;}\\
 102 \hlline{50\ }\hlstd{\ }\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{}\hlkwa{true}\hlstd{}\hlsym{)\ \{}\\
 103 \hlline{51\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwd{forn\ }\hlstd{}\hlsym{(}\hlstd{i}\hlsym{,\ }\hlstd{buf\textunderscore size}\hlsym{)\ \{}\\
 104 \hlline{52\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{state\ }\hlsym{==\ }\hlstd{final}\hlsym{)\ \{}\\
 105 \hlline{53\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{cout\ }\hlsym{$<$$<$\ (}\hlstd{pos\ }\hlsym{+\ }\hlstd{i\ }\hlsym{{-}\ }\hlstd{final}\hlsym{)\ $<$$<$\ }\hlstd{}\hlstr{"\ "}\hlstd{}\hlsym{;}\\
 106 \hlline{54\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlsym{\}}\\
 107 \hlline{55\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{s}\hlsym{{[}}\hlstd{state}\hlsym{{]}\ !=\ }\hlstd{buf}\hlsym{{[}}\hlstd{i}\hlsym{{]})\ \{}\\
 108 \hlline{56\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{state\ }\hlsym{=\ }\hlstd{f}\hlsym{{[}}\hlstd{state}\hlsym{{]};}\\
 109 \hlline{57\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{state\ }\hlsym{==\ {-}}\hlstd{}\hlnum{1}\hlstd{}\hlsym{)\ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 110 \hlline{58\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlsym{\}}\\
 111 \hlline{59\ }\hlstd{}\hlstd{\ \ \ }\hlstd{state}\hlsym{++;}\\
 112 \hlline{60\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}}\\
 113 \hlline{61\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{buf\textunderscore size\ }\hlsym{$<$\ }\hlstd{TAMBUF}\hlsym{)\ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 114 \hlline{62\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwd{buf\textunderscore sync}\hlstd{}\hlsym{();}\\
 115 \hlline{63\ }\hlstd{\ }\hlsym{\}}\\
 116 \hlline{64\ }\hlstd{}\hlsym{\}}\\
 117 \hlline{65\ }\hlstd{}\\
 118 \hlline{66\ }\hlkwb{int\ }\hlstd{}\hlkwd{main}\hlstd{}\hlsym{()\ \{}\\
 119 \hlline{67\ }\hlstd{\ }\hlkwa{for\ }\hlstd{}\hlsym{(;;)\ \{}\\
 120 \hlline{68\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwb{int\ }\hlstd{needle\textunderscore size}\hlsym{;}\\
 121 \hlline{69\ }\hlstd{}\hlstd{\ \ }\hlstd{string\ needle}\hlsym{;}\\
 122 \hlline{70\ }\hlstd{}\hlstd{\ \ }\hlstd{cin\ }\hlsym{$>$$>$\ }\hlstd{needle\textunderscore size}\hlsym{;}\\
 123 \hlline{71\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{cin}\hlsym{.}\hlstd{}\hlkwd{eof}\hlstd{}\hlsym{())\ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 124 \hlline{72\ }\hlstd{}\hlstd{\ \ }\hlstd{cin\ }\hlsym{$>$$>$\ }\hlstd{needle}\hlsym{;}\\
 125 \hlline{73\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwd{assert}\hlstd{}\hlsym{(}\hlstd{needle\textunderscore size\ }\hlsym{==\ }\hlstd{needle}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{());}\\
 126 \hlline{74\ }\hlstd{}\hlstd{\ \ }\hlstd{cin}\hlsym{.}\hlstd{}\hlkwd{ignore}\hlstd{}\hlsym{(}\hlstd{}\hlnum{1}\hlstd{}\hlsym{);}\\
 127 \hlline{75\ }\hlstd{\\
 128 \hlline{76\ }}\hlstd{\ \ }\hlstd{vint\ }\hlkwd{f}\hlstd{}\hlsym{(}\hlstd{needle}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{()\ +\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{);}\\
 129 \hlline{77\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwd{pkmp}\hlstd{}\hlsym{(}\hlstd{needle}\hlsym{,\ }\hlstd{f}\hlsym{);}\\
 130 \hlline{78\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwd{kmp}\hlstd{}\hlsym{(}\hlstd{needle}\hlsym{,\ }\hlstd{f}\hlsym{);}\\
 131 \hlline{79\ }\hlstd{}\hlstd{\ \ }\hlstd{cout\ }\hlsym{$<$$<$\ }\hlstd{endl}\hlsym{;}\\
 132 \hlline{80\ }\hlstd{\ }\hlsym{\}}\\
 133 \hlline{81\ }\hlstd{\ }\hlkwa{return\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{;}\\
 134 \hlline{82\ }\hlstd{}\hlsym{\}}\\
 135 \hlline{83\ }\hlstd{}\\
 136 \mbox{}
 137 \normalfont
 138 \shorthandon{"}
 139